package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.LinkedList;

/**
 * Created by dp on 17/3/27.
 */
public class ReConstructBinaryTree {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) throws Exception {
        TreeNode root = doReConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return root;
    }

    private TreeNode doReConstructBinaryTree(int[] pre, int preLeft, int preRight, int[] in, int inLeft, int inRight) throws Exception {
        TreeNode node = new TreeNode(pre[preLeft]);

        if (preLeft == preRight) {
            if (inLeft == inRight && in[inLeft] == pre[preLeft]) {
                return node;
            } else {
                throw new Exception("不合法");
            }
        }

        int i = inLeft;
        for (; i < inRight; i++) {
            if (in[i] == pre[preLeft]) {
                break;
            }
        }

        int length = i - inLeft;
        if (length > 0) {
            node.left = doReConstructBinaryTree(pre, preLeft + 1, preLeft + length, in, inLeft, i - 1);
        }
        if (length < preRight - preLeft) {
            node.right = doReConstructBinaryTree(pre, preLeft + length + 1, preRight, in, i + 1, inRight);
        }
        return node;
    }

    public void printTree(TreeNode root) {
        if (root == null) return;
        TreeNode treeNode = new TreeNode(Integer.MAX_VALUE);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            TreeNode pop = queue.pop();
            if (pop == treeNode) {
                if (queue.isEmpty()) return;
                queue.add(treeNode);
                System.out.println();
            } else {
                System.out.print(pop.val + "\t");
                TreeNode left = pop.left;
                if (left != null) {
                    queue.add(left);
                }
                TreeNode right = pop.right;
                if (right != null) {
                    queue.add(right);
                }
            }
        }

    }

    public static void main(String[] args) throws Exception {
        int[] pre = {1, 2, 4, 5, 3, 6, 7};
        int[] in = {4, 2, 5, 1, 6, 3, 7};
        ReConstructBinaryTree reConstructBinaryTree = new ReConstructBinaryTree();
        TreeNode treeNode = reConstructBinaryTree.reConstructBinaryTree(pre, in);
        reConstructBinaryTree.printTree(treeNode);
    }

}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}
